package first_practice;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-105-从前序与中序遍历序列构造二叉树
 * @date 2025/4/16 15:46
 */
public class Solution105 {
    private Map<Integer, Integer> inorderIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 为中序遍历建立哈希表
        for (int i = 0; i < inorder.length; i++) {
            inorderIndex.put(inorder[i], i);
        }
        return myBuildTree(preorder, 0, n - 1, 0);
    }

    private TreeNode myBuildTree(int[] preorder, int preOrderLeft, int preOrderRight, int inorderLeft) {
        if (preOrderLeft > preOrderRight) {
            // 没有节点了
            return null;
        }
        int rootVal = preorder[preOrderLeft];
        TreeNode root = new TreeNode(rootVal);
        int rootIdx = inorderIndex.get(rootVal);
        int leftTreeLen = rootIdx - inorderLeft; // 左子树的节点个数

        root.left = myBuildTree(preorder, preOrderLeft + 1,
                preOrderLeft + leftTreeLen, inorderLeft);

        root.right = myBuildTree(preorder, preOrderLeft + leftTreeLen + 1,
                preOrderRight, rootIdx + 1);

        return root;
    }
}
